//
// Created by francklinson on 2021/7/13 AT 23:29.
//

//给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
//
//两个相邻元素间的距离为 1 。
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    // 从1开始
    vector<vector<int>> updateMatrix(vector<vector<int>> &mat) {
        unsigned int m = mat.size(), n = mat[0].size();
        vector<vector<int>> ansMat(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 0) ansMat[i][j] = 0;
                else ansMat[i][j] = BFS(mat, i, j);
            }
        }
        return ansMat;
    }

    int BFS(vector<vector<int>> &mat, int i, int j) {
        const vector<pair<int, int>> movement{{1,  0},
                                              {-1, 0},
                                              {0,  1},
                                              {0,  -1}};
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int range = 0;
        while (!q.empty()) {
            ++range;
            int levelSize = q.size();
            for (int k = 0; k < levelSize; ++k) {
                auto p = q.front();
                q.pop();
                for (int l = 0; l < 4; ++l) {
                    int nr = p.first + movement[l].first;
                    int nc = p.second + movement[l].second;
                    if (nr >= 0 and nr < mat.size() and nc >= 0 and nc < mat[0].size()) {
                        if (mat[nr][nc] == 0) {
                            return range;
                        } else
                            q.emplace(nr, nc);
                    }
                }
            }
        }
        return range;
    }
};

class Solution2 { // 题解 从0开始
private:
    const int dirs[4][2] = {{-1, 0},
                                {1,  0},
                                {0,  -1},
                                {0,  1}};

public:
    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<int>> seen(m, vector<int>(n));
        queue<pair<int, int>> q;
        // 将所有的 0 添加进初始队列中 多源bfs
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    q.emplace(i, j);
                    seen[i][j] = 1;
                }
            }
        }

        // 广度优先搜索
        while (!q.empty()) {
            auto p = q.front();
            auto i = p.first, j = p.second;
            q.pop();
            for (int d = 0; d < 4; ++d) {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.emplace(ni, nj);
                    seen[ni][nj] = 1;
                }
            }
        }

        return dist;
    }
};


int main() {
    vector<vector<int>> mat{{0, 0, 0},
                            {0, 1, 0},
                            {0, 0, 0}};
    Solution2 solution;
    auto ans = solution.updateMatrix(mat);
    for (auto &r:ans) {
        for (auto &c:r) {
            cout << c;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}

